package main

import (
	"errors"
	"fmt"
	"strconv"
)

//使用数组模拟栈的使用
type Stack struct {
	MaxTop int     //表示栈能存放的最大值
	Top    int     //表示栈顶
	arr    [20]int //数组模拟栈
}

func (s *Stack) Push(val int) (err error) {
	//先判断栈是否已经满了
	if s.Top == s.MaxTop-1 {
		fmt.Println("stack full")
		return errors.New("stack full")
	}
	s.Top++
	//放入数据
	s.arr[s.Top] = val
	return err
}

//出栈
func (s *Stack) Pop() (val int, err error) {
	//判断栈是不是空的
	if s.Top == -1 {
		fmt.Println("stack empty")
		return 0, errors.New("stack empty")
	}
	//先取值，在top--
	val = s.arr[s.Top]
	s.Top--
	return val, nil
}

//遍历栈，需要从栈顶开始遍历
func (s *Stack) Show() {
	//先判断栈是否为空
	if s.Top == -1 {
		fmt.Println("stack empty")
		return
	}
	for i := s.Top; i >= 0; i-- {
		fmt.Printf("arr[%d]=%d\n", i, s.arr[i])
	}
}

//判断一个字符是不是一个运算符
func (s *Stack) IsOper(val int) bool {
	if val == 42 || val == 43 || val == 45 || val == 47 {
		return true
	} else {
		return false
	}
}

//运算的方法
func (s *Stack) Cal(num1 int, num2 int, oper int) int {
	res := 0
	switch oper {
	case 42:
		res = num2 * num1
	case 43:
		res = num2 + num1
	case 45:
		res = num2 - num1
	case 47:
		res = num2 / num1
	default:
		fmt.Println("运算符错误")
	}
	return res
}

//编写一个方法，返回运算符的优先级
func (s *Stack) Priority(oper int) int {
	res := 0
	if oper == 42 || oper == 47 {
		res = 1
	} else if oper == 43 || oper == 45 {
		res = 0
	}
	return res

}

func main() {
	//数栈
	numStack := &Stack{
		MaxTop: 20,
		Top:    -1,
	}
	//符号栈
	operStack := &Stack{
		MaxTop: 20,
		Top:    -1,
	}

	exp := "3+20*6/2-2"
	//定义一个index，帮助扫描
	index := 0
	//为了配合运算，我们定义需要的变量
	num1 := 0
	num2 := 0
	oper := 0
	result := 0
	keepNum := ""

	for {
		//这里我们需要增加一个逻辑

		ch := exp[index : index+1]
		temp := int([]byte(ch)[0])
		if operStack.IsOper(temp) {
			//如果operStack是一个空栈，直接入栈
			if operStack.Top == -1 {
				operStack.Push(temp)
			} else {
				//如果发现operStack栈顶运算符的优先级大于等于当前准备入栈的运算符的优先级
				//就从符号栈pop出，并从数栈也pop两个数据，进行运算，运算后的结果在重新入栈
				//到数栈，符号再入符号栈
				if operStack.Priority(operStack.arr[operStack.Top]) >= operStack.Priority(temp) {
					num1, _ = numStack.Pop()
					num2, _ = numStack.Pop()
					oper, _ = operStack.Pop()
					result = operStack.Cal(num1, num2, oper)
					//将计算的结果重新入栈
					numStack.Push(result)
					//将当前的符号打入符号栈
					operStack.Push(temp)
				} else {
					operStack.Push(temp)
				}
			}
		} else {
			//处理多为数的思路
			//1、定义一个变量，keepNum string，做拼接
			//2、每次要向index的前面字符测试一下，看看是不是运算符，然后处理
			keepNum += ch
			//如果已经到表达式最后，直接将keepNum
			if index == len(exp)-1 {
				val, _ := strconv.ParseInt(keepNum, 10, 64)
				numStack.Push(int(val))
			} else {
				if operStack.IsOper(int([]byte(exp[index+1 : index+2])[0])) {
					val, _ := strconv.ParseInt(keepNum, 10, 64)
					numStack.Push(int(val))
					keepNum = ""
				}

			}

			//val,_ := strconv.ParseInt(ch,10,64)
			//numStack.Push(int(val))
		}
		//继续扫描
		//先判断index是否已经扫描到计算表达式的最后
		if index+1 == len(exp) {
			break
		} else {
			index++
		}
	}

	//如果扫描表示字符串完毕，依次从符号栈取出符号，然后从数栈取出两个数字
	//运算后的结果，入数栈，直到符号栈为空
	for {
		if operStack.Top == -1 {
			break
		}
		num1, _ = numStack.Pop()
		num2, _ = numStack.Pop()
		oper, _ = operStack.Pop()
		result = operStack.Cal(num1, num2, oper)
		numStack.Push(result)
	}
	//如果我们的算法没有问题，表达式也是正确，则结果就是numStack租后数
	res, _ := numStack.Pop()
	fmt.Println("表达式最后的结果为", res)
}
